import java.util.Scanner;

public class demo02 {
//    public static void main(String[] args) {
//        Scanner sc=new Scanner(System.in);
//        while (sc.hasNext()){
//            int n=sc.nextInt();
//            sc.nextLine();
//            int a=1;
//            int b=1;
//            int c=1;
//            while (n>1){
//                c=a+b;
//                c%=1000000;
//                a=b;
//                b=c;
//                n--;
//            }
//            System.out.println(b);
//        }
//    }


    //斐波那契凤尾
    public static void main(String[] args) {
        int border=-1;
        long[] arr=new long[100000];
        arr[0]=1;
        arr[1]=2;
        for (int i = 2; i < 100000; i++) {
            long num=arr[i-1]+arr[i-2];
            if(border==-1&&num>=1000000){
                border=i+1;
            }
            arr[i]=num%1000000;
        }
        Scanner sc=new Scanner(System.in);
        while (sc.hasNext()){
            int n=sc.nextInt();
            long m=arr[n-1];
            if(n<border){
                System.out.printf("%d\n",m);
            }else{
                System.out.printf("%06d\n",m);
            }
        }
    }
}
